% Authors: Francisco Pinto & Bruno Maia
% Date: 22-09-2011
%
% This file is part of "Breakthrough"

% Minimax implement for the game's AI

?- ensure_loaded('constants.pro').
?- ensure_loaded('breakthrough.pro').

% minimax/4 / minimax/5
% Modes: (+,+,-,+) / (+,+,-,-,+)
% Recursive minimax implement which finds the best move 
% Player can make in Board at a tree-depth of Depth 
minimax(Player, Board, NewBoard, Depth) :-
  opposing_player(Player, Opposing),
  minimax(Opposing, Board, NewBoard, _, Depth).

minimax(_, Board, Board, Val, 0) :-
  first(First),
  evaluate_board(Board, First, Val).

minimax(Player, Board, BestSucc, Val, Depth)  :-
  Depth > 0,
  NewDepth is Depth - 1,
  opposing_player(Player, Opposing),
  moves(Board, Opposing, BoardList), !,
  best(Opposing, BoardList, BestSucc, Val, NewDepth)
    ;
    (
      first(First),
      static_evaluate_board(Board, First, Val)
    ).

% best/5
% Modes: (+,+,-,-,+)
% Out of a list of boards, this predicate finds the "best" one
best(Player, [Board], Board, Val, Depth)  :-
  minimax(Player, Board, _, Val, Depth), !.

best(Player, [Board1 | BoardList], BestBoard, BestVal, Depth)  :-
  minimax(Player, Board1, _, Val1, Depth),
  best(Player, BoardList, Board2, Val2, Depth),
  better_of(Player, Board1, Val1, Board2, Val2, BestBoard, BestVal).

% min_to_move/1
% Modes: (+)
% True if Player is the minimizing faction in the minimax algorithm
min_to_move(Player) :-
  \+first(Player).

% max_to_move/1
% Modes: (+)
% True if Player is the maximizing faction in the minimax algorithm
max_to_move(Player) :-
  first(Player).

% better_of/7
% Modes: (+,+,+,+,+,-,-)
% Finds the best out of two boards
better_of(Player, Board0, Val0, _, Val1, Board0, Val0) :-
  min_to_move(Player),
  Val0 < Val1, !
  ;
    max_to_move(Player),
    Val0 > Val1, !.

better_of(_, _, _, Board1, Val1, Board1, Val1).